0% completed
Problem Statement
Given a string s and integer k, return true if string can be converted into the palindromic string after removing at most k characters. Otherwise, return false.
Examples
-
Example 1:
- Input:
s = "rdar", k = 1 - Expected Output:
true - Justification: We can make
rdarto palindromic by removing eitherdoracharacter.
- Input:
-
Example 2:
- Input:
s = "abracadabra", k = 5 - Expected Output:
true - Justification: By removing the characters 'b', 'c', 'd', and 'b' , the string becomes "araaara", which is a palindrome. We've removed exactly 5 characters, so the output is
true.
- Input:
-
Example 3:
- Input:
s = "data", k = 0 - Expected Output:
false - Justification: It's impossible to form a palindrome by removing zero characters from "data", so the output is
false.
- Input:
Constraints:
- 1 <= s.length <= 1000
- s consists of only lowercase English letters.
- 1 <= k <= s.length
Solution
To solve this problem, we will use dynamic programming to keep track of the minimum number of characters that need to be removed to make any substring a palindrome. The core idea is to compare characters from both ends of the string and move towards the center, while keeping track of the minimum deletions needed at each step. This approach works because a palindrome reads the same forwards and backwards, so we can strategically remove characters that disrupt this symmetry. By building up solutions for smaller substrings and using these to solve larger substrings, we ensure efficiency and avoid redundant calculations. The use of dynamic programming is effective here because it breaks down the larger problem into manageable sub-problems, each of which is solved only once.
Step-by-step Algorithm
- Create a 2D array
dpwheredp[i][j]represents the minimum number of deletions needed to make the substring from indexitoja palindrome. - Initialize
dp[i][i]to 0 for alli, as a single character is always a palindrome. - For substrings of length 2 to
n(wherenis the length of the string):- For each starting index
i, calculate the ending indexj = i + length - 1. - If the characters at
iandjare the same, setdp[i][j]todp[i + 1][j - 1](no additional deletions needed). - If they are different, set
dp[i][j]to the minimum ofdp[i + 1][j]anddp[i][j - 1]plus 1 (delete eitheriorjcharacter).
- For each starting index
- Check if
dp[0][n - 1]is less than or equal tok. If yes, returntrue, else returnfalse.
Algorithm Walkthrough 1
Let's consider the input s = "data", k = 0
-
Initialization:
s = "data"has a length ofn = 4.- Initialize a 2D array
dpof size4x4with all values set to0.
-
Filling the DP Array:
- The
dparray is filled such thatdp[i][j]represents the minimum number of deletions needed to make the substring from indexitoja palindrome. - Initially, all
dp[i][i]are0since a single character is always a palindrome.
- The
-
Iterating Over Substrings:
- We consider substrings of increasing lengths. For each substring length (from 2 to
n), we check every possible substring of that length and update thedparray accordingly.
- We consider substrings of increasing lengths. For each substring length (from 2 to
-
Filling
dpfors = "data":- Substring Length
2:- Compare
s[0]('d') withs[1]('a'): Since they are different,dp[0][1] = 1 + min(dp[0][0], dp[1][1]) = 1. - Compare
s[1]('a') withs[2]('t'): Since they are different,dp[1][2] = 1 + min(dp[1][1], dp[2][2]) = 1. - Compare
s[2]('t') withs[3]('a'): Since they are different,dp[2][3] = 1 + min(dp[2][2], dp[3][3]) = 1.
- Compare
- Substring Length
3:- Compare
s[0]withs[2]: Since they differ,dp[0][2] = 1 + min(dp[0][1], dp[1][2]) = 2. - Compare
s[1]withs[3]: Since they are the same,dp[1][3] = dp[1 + 1][3 - 1] = dp[2][2] = 0.
- Compare
- Substring Length
4:- Compare
s[0]withs[3]: Since they are different,dp[0][3] = 1 + min(dp[0][2], dp[1][3]) = 1.
- Compare
- Substring Length
-
Final DP Matrix:
- After filling in the values, the
dpmatrix looks like this:0 1 2 1 0 0 1 0 0 0 0 1 0 0 0 0
- After filling in the values, the
-
Checking the Result:
- We need to check if
dp[0][n - 1](which isdp[0][3]in this case) is less than or equal tok. dp[0][3]is1, which is not less than or equal tok(0in this case).- Therefore, the final result is
false: it is not possible to turns = "data"into a palindrome without deletions, as per thek = 0constraint.
- We need to check if
Algorithm Walkthrough 2
Let's consider the input s = "rdar" and k = 1.
-
Initialization:
s = "rdar"has a length ofn = 4.- Initialize a 2D array
dpof size4x4with all values set to0.
-
Filling the DP Array:
- The
dparray is filled such thatdp[i][j]represents the minimum number of deletions needed to make the substring from indexitoja palindrome. - Initially, all
dp[i][i]are0since a single character is always a palindrome.
- The
-
Iterating Over Substrings:
- We consider substrings of increasing lengths. For each substring length (from 2 to
n), we check every possible substring of that length and update thedparray accordingly.
- We consider substrings of increasing lengths. For each substring length (from 2 to
-
Filling
dpfors = "rdar":- Substring Length
2:- Compare
s[0]('r') withs[1]('d'): Since they are different,dp[0][1] = 1 + min(dp[0][0], dp[1][1]) = 1. - Compare
s[1]('d') withs[2]('a'): Since they are different,dp[1][2] = 1 + min(dp[1][1], dp[2][2]) = 1. - Compare
s[2]('a') withs[3]('r'): Since they are different,dp[2][3] = 1 + min(dp[2][2], dp[3][3]) = 1.
- Compare
- Substring Length
3:- Compare
s[0]withs[2]: Since they are different,dp[0][2] = 1 + min(dp[0][1], dp[1][2]) = 2. - Compare
s[1]withs[3]: Since they are different,dp[1][3] = 1 + min(dp[1][2], dp[2][3]) = 2.
- Compare
- Substring Length
4:- Compare
s[0]withs[3]: Since they are the same,dp[0][3] = dp[1][2] = 1. (The characters at the beginning and end match, so we check the inner substring "da").
- Compare
- Substring Length
-
Final DP Matrix:
- After filling in the values, the
dpmatrix looks like this:0 1 2 1 0 0 1 2 0 0 0 1 0 0 0 0
- After filling in the values, the
-
Checking the Result:
- We need to check if
dp[0][n - 1](which isdp[0][3]in this case) is less than or equal tok. dp[0][3]is1, which is equal tok(1in this case).- Therefore, the final result is
true: it is possible to turns = "rdar"into a palindrome by making at most1deletion.
- We need to check if
Code
Complexity Analysis
-
Time Complexity:
- The algorithm uses a nested loop structure where both the outer and inner loops iterate over the string length
n. This results in a quadratic time complexity as each character is compared with others in different combinations.
- The algorithm uses a nested loop structure where both the outer and inner loops iterate over the string length
-
Space Complexity:
- A 2D array
dpof sizen x nis used for dynamic programming, wherenis the length of the string.
- A 2D array
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough 1
Algorithm Walkthrough 2
Code
Complexity Analysis